class Solution {
  public:
    int findKthElementHelper(int A[], int m, int B[], int n, int K) { // K = 1, 2, ....
      int low = (n < K ? K - n - 1 : 0);
      int high = (m > K ? K - 1 : m - 1);
      int mid = 0;

      while (low <= high) {
        mid = (low + high) / 2;
        int pre = (K - mid - 2 < 0 ? numeric_limits<int>::min() : B[K - mid - 2]);
        int post = (K - mid - 1 >= n ? numeric_limits<int>::max() : B[K - mid - 1]);
        if (pre <= A[mid] && A[mid] <= post) {
          return mid;
        } else if (A[mid] > post) {
          high = mid - 1;
        } else {
          low = mid + 1;
        }

      }
      return -1;
    }

    int findKthElement(int A[], int m, int B[], int n, int K) {
      if (m == 0) {
        return B[K - 1];
      } else if (n == 0) {
        return A[K - 1];
      } else {
        int index = findKthElementHelper(A, m, B, n, K);
        if (index >= 0) {
          return A[index];
        }
        index = findKthElementHelper(B, n, A, m, K);
        return B[index];
      }
    }

    double findMedianSortedArrays(int A[], int m, int B[], int n) {
      // Start typing your C/C++ solution below
      // DO NOT write int main() function
      if ((m + n) % 2 == 0) {
        return (findKthElement(A, m, B, n, (m + n) / 2) +
            findKthElement(A, m, B, n, (m + n) / 2 + 1)) / 2.0;
      } else {
        return findKthElement(A, m, B, n, (m + n) / 2 + 1);
      }
    }
};
